package com.heap;

/**
 * 最大堆:
 *      >这里使用 data[] 数组来保存最大堆,data[0]不使用,data[1]表示根节点,data[2]表示根节点左子树中的根节点,依次类推
 * 性质:
 *      >最大堆满足完全二叉树的性质
 *      >父节点的值大于两个子节点
 * 如果使用数组下标 1 存储第一个元素
 *      >下标为 k 的节点的父节点为 k / 2;
 *      >下标为 k 的节点的左孩子为 2 * k;
 *      >下标为 k 的节点的右孩子为 2 * k + 1;
 * 如果使用数组下标 0 存储第一个元素
 *      >下标为 k 的节点的父节点为 (k - 1) / 2;
 *      >下标为 k 的节点的左孩子为 2 * k + 1;
 *      >下标为 k 的节点的右孩子为 2 * k + 2;
 */
public class MaxHeap implements IMaxHeap {

    private int[] data; //最大堆的载体,使用数组来承载
    private int num;    //记录传入的最大空间,防止数组越界
    private int count;  //记录已经存储的数量

    //插入元素时使用,注意 k 表示下标
    private void shiftUp(int k) {
        //循环的检查它是否大于父节点,如果大于父节点,就要交换它(data[k])与父节点(data[k/2])的位置,来满足最大堆的定义
        while ((data[k / 2] < data[k]) && (k > 1)) {
            //交换 data[k/2] 与 data[k]
            int temp = data[k / 2];
            data[k / 2] = data[k];
            data[k] = temp;
            //更新k,现在data[k/2]即为新插入的那个值
            k /= 2;
        }
    }

    //删除节点时使用,注意 k 表示下标
    private void shiftDown(int k) {
        //循环的执行shiftDown操作,判断条件是 data[k] 有孩子
        //现在需要将 data[k] 的孩子中找出最大值,与 data[k]交换位置
        while (2 * k <= count) {
            int j = 2 * k;  //表示此轮循环中, data[k] 要和 data[j] 交换位置
            //如果它有右孩子并且右孩子比左孩子大,那么就要更新 j ,一会交换 data[k] 与 data[j+1] 的位置
            if (2 * k + 1 <= count && data[j + 1] > data[j]) {
                j += 1;
            }
            //如果 data[k] 比即将交换位置的值(子树中的最大值)要大,证明现在已经是最大堆了,退出循环
            if (data[k] >= data[j]) {
                break;
            }
            //交换 data[k] 与 data[j]
            int temp = data[k];
            data[k] = data[j];
            data[j] = temp;
            //更新 k 的位置,在进行新一轮的交换,直到整个结构满足最大堆的性质
            k = j;
        }
    }

    public int getCount() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }


    //插入新的元素
    public void insert(int item) {

        //防止数组越界
        assert count + 1 <= num;
        //将新加入的数据放在堆的末尾,然后使用完全二叉树的性质进行排序
        data[count + 1] = item;
        count++;
        shiftUp(count);
    }

    //删除最大的节点,即删除 data[1],然后使整个二叉树仍然保持最大堆的性质
    public int extrackMax() {
        assert count > 0;
        //删除节点时,首先将最后一个元素 (data[count]) 覆盖掉第一个节点,然后通过 shiftDown 函数使整个二叉树满足最大堆
        int item = data[1];
        data[1] = data[count];
        count--;
        shiftDown(1);
        return item;
    }

    public int[] sortInside() {
        //将已经得到的最大堆的第一个值 (data[1])与最后一个值进行交换,然后执行ShiftDown操作,保证它依旧是个最大堆就好
        for (int i = 1; i <= num; i++) {
            //交换data[1] 与 data[count] 的位置
            int temp = data[1];
            data[1] = data[count];
            data[count] = temp;
            count--;
            shiftDown(1);
        }

        return data;
    }

    public MaxHeap(int num) {
        data = new int[num + 1];
        this.count = 0;
        this.num = num;
    }

    public MaxHeap(int[] arr) {
        data = new int[arr.length + 1];
        this.num = arr.length;
        //这里不在插入数据时保证最大堆
        for (int i = 0; i < num; i++) {
            data[i + 1] = arr[i];
        }
        count = num;
        //从第一个拥有子节点的节点( arr[count / 2] )开始进行shiftDown操作,逐渐往上遍历
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i);
        }
    }


}
















